package tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class TreeProblem {
    //迭代实现中序遍历（栈）.push left到left为null，pop出来一个，加入list
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root == null)
            return list;
        stack.push(root);
        TreeNode currentNode = root.left;
        while (currentNode != null || !stack.empty()) {
            while (currentNode != null) {
                stack.push(currentNode);
                currentNode = currentNode.left;
            }
            currentNode = stack.pop();
            list.add(currentNode.val);
            currentNode = currentNode.right;
        }

        return list;
    }

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode currentNode = root;
        while (currentNode != null || !stack.empty()) {
            while (currentNode != null) {
                list.add(currentNode.val);
                stack.push(currentNode);
                currentNode = currentNode.left;
            }
            currentNode = stack.pop();
            currentNode = currentNode.right;
        }

        return list;
    }

    // 后序非递归，关键在于判断节点是否已被遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode currentNode = root;
        TreeNode lastNode = null;
        while (currentNode != null || !stack.empty()) {
            while (currentNode != null && currentNode != lastNode) {
                stack.push(currentNode);
                currentNode = currentNode.left;
            }
            // 无右节点，且未被遍历
            if (stack.peek().right == null && stack.peek() != lastNode) {
                lastNode = stack.pop();
                list.add(lastNode.val);
                //右节点已被遍历
            } else if (stack.peek().right == lastNode) {
                lastNode = stack.pop();
                list.add(lastNode.val);
            } else currentNode = stack.peek().right;
        }

        return list;
    }
}
